2021 Algorithm                       < No.8 이상한 놈>                  Prof. Zoh Q.

2022 Algorithm                         < No.14 단편>                         Prof. Zoh Q.

조각난 fragment를 이용하여 원래의 서열을 추정하는 fragment assembly 작업의 과정을 보여주는 한 예

단편(fragment)

[문제]   생물의 유전체(Genome) 실험 도중에는 다양한 크기의 DNA 단편(fragmentation)이 생성된다. 전체 유전체의 원래 서열은 이 단편을 다양한 방법으로 조합하여 예측하는데 이 과정을 보통 Genome assembly라고 한다. 이 단계에는 반드시 생성된 단편을 정렬(sorting)하여 서로 유사한 것이 있는지를 확인하는 과정이 필요하다. 특히 단편의 개수가 수천만 개일 경우 이 작업은 상당한 메모리와 시간이 걸리는 작업이 된다.

단편은 5개의 문자 {a, c, g, t, n}으로 구성된 문자열(string)로 생각할 수 있다. 우리는 이 단편을 사전식으로 정렬했을 때 [eqn: k-1, ``k, ``k+1~]번째에 해당하는 fragment를 찾으려고 한다. 출력으로는 [eqn: k-1, ``k, ``k+1~]번째에 해당하는 3개 단편의 원래 입력에서의 순서(index)를 출력해야 한다.

아래와 같이 입력으로 12개의 단편이 주어져 있다고 가정하자. 이들을 사전식으로 정렬하면 아래 표의 중앙과 같다. 입력의 첫 줄에는 정수 [eqn: k]가 주어진다. 전체 단편의 수를 [eqn: n]개라고 했을 때, 여러분이 찾아야 하는 순서의 중앙값 [eqn: k]의 범위는 [eqn: 2 leq k leq n-1] 이다. 아래와 같을 경우 [eqn: k=7]일 때 해당하는 단편은 굵은 파란색으로 표시된 단편이다. 따라서 답은 입력에 주어진 단편의 index인 5, 2, 4를 출력해야 한다.

stdin	fragments sorted	stdout
7 #[eqn: k] ctgaatgaccnna #[eqn: f_1] gtatcga #[eqn: f _{2}] agtctgcaatg gttactaganngata #[eqn: f _{4}] cttaaagttaacccgta #[eqn: f _{5}] tgaaccgtaga agcctga ttattattaaagtaga tcgga #[eqn: f _{9}] aattttggggaaaattttgg ccctgnngtaga #[eqn: f _{11}]	aattttggggaaaattttgg agcctga agtctgcaatg ccctgnngtaga #[eqn: f _{11}] ctgaatgaccnna #[eqn: f_1] cttaaagttaacccgta#[eqn: f _{5}] gtatcga #[eqn: f _{2}] gttactaganngata #[eqn: f _{4}] tcgga #[eqn: f _{9}] tgaaccgtaga ttattattaaagtaga	5 2 4

[입출력]   입력과 출력은 표준입출력을 사용한다. 첫 줄에 정수 [eqn: k]가 나온다. 각 DNA 단편으로 제시되는 문자열의 길이 L의 범위는 [eqn: 10` LEQ `L leq 100] 이다. 그리고 입력에 제공되는 전체 단편의 수 [eqn: n]의 범위는 [eqn: 10` LEQ n LEQ 500,000]로 최대 50만 개까지 입력될 수 있다.

[도움]   프로그램 이름은 fragment.{c,cpp,py}. 이 문제의 핵심은 전체 fragment 모두 정렬하지 않고 radix를 적절히 이용해서 3개의 [eqn: k-1, ``k, ``k+1~]번째의 단편만 찾는 것이다. 즉 단편의 radix를 앞에서부터 하나씩 살펴보면서 탐색 범위를 줄여가야 한다.

수행시간은 test case당 최대 1초이며, 코드의 최대 크기는 3000 bytes이다. Python이나 C/C++에서 제공하는 generic sort( )를 사용해서 풀면 0점 처리되므로 유의하기 바랍니다.

입력 데이터가 상당히 크므로 입력하는 과정도 신경을 써야 한다. 이런 문제에서 입력하는 과정에서 느슨하게 할 경우 여기에 모든 시간을 다 잡아먹는 수가 있기 때문이다.